package heap;

import java.util.ArrayList;
import java.util.List;

/**
 * 
 * @author 26233
 * 大根堆数组实现
 */
public class SmallRootHeap {
	
	// 数组扩容交给List系统处理
	List<Integer> smallHeapArray = new ArrayList<Integer>();
	
	int count = 0;
	
	// 根据有限数据构造
	public void init(int[] data) {
		for(int i = 0; i < data.length; i++) {
			smallHeapArray.add(data[i]);
			heapfyUp(smallHeapArray);
			count++;
		}
		
	}
	
	// 根据不确定数量数据构造
	public void add(int data) {
		smallHeapArray.add(data);
		heapfyUp(smallHeapArray);
		count++;
	}
	
	public int pop() {
		
		int result = smallHeapArray.get(0);
		int lastIndex = smallHeapArray.size() - 1;
		smallHeapArray.set(0, smallHeapArray.get(lastIndex));
		smallHeapArray.remove(lastIndex);
		
		heapfyDown(smallHeapArray);
		
		count--;
		return result;
	}
	
	public void delete(int data) {}
	
	// 删除头元素时，末尾元素交换到头元素位置，然后向下调整
	public void heapfyDown(List<Integer> smallHeapArray) {
		int index = 0;
		while(index < smallHeapArray.size()) {
			int leftChildIndex = index * 2 + 1;
			int rightChildIndex = index * 2 + 2;
			
			if(leftChildIndex >= smallHeapArray.size() && rightChildIndex >= smallHeapArray.size()) {
				break;
			}else {
				if(leftChildIndex >= smallHeapArray.size()) {
					if(smallHeapArray.get(rightChildIndex) < smallHeapArray.get(index)) {
						int temp = smallHeapArray.get(rightChildIndex);
						smallHeapArray.set(rightChildIndex, smallHeapArray.get(index));
						smallHeapArray.set(index, temp);
						
						index = rightChildIndex;
					}else {
						break;
					}
				}else if(rightChildIndex >= smallHeapArray.size()) {
					if(smallHeapArray.get(leftChildIndex) < smallHeapArray.get(index)) {
						int temp = smallHeapArray.get(leftChildIndex);
						smallHeapArray.set(leftChildIndex, smallHeapArray.get(index));
						smallHeapArray.set(index, temp);
						
						index = leftChildIndex;
					}else {
						break;
					}
				}else {
					int maxIndex = index;
					if(smallHeapArray.get(leftChildIndex) < smallHeapArray.get(maxIndex)) {
						maxIndex = leftChildIndex;
					}
					if(smallHeapArray.get(rightChildIndex) < smallHeapArray.get(maxIndex)) {
						maxIndex = rightChildIndex;
					}
					
					if(maxIndex == index) {
						break;
					}else {
						
						int temp = smallHeapArray.get(maxIndex);
						smallHeapArray.set(maxIndex, smallHeapArray.get(index));
						smallHeapArray.set(index, temp);
						
						index = maxIndex;
					}
				}
			}
			
		}
	}
	
	// 添加元素后向上调整
	public void heapfyUp(List<Integer> smallHeapArray) {
		int index = smallHeapArray.size() - 1;
		while(index > 0) {
			if(smallHeapArray.get((index -1) / 2) > smallHeapArray.get(index)) {
				// 交换
				int temp = smallHeapArray.get(index);
				smallHeapArray.set(index, smallHeapArray.get((index -1) / 2));
				smallHeapArray.set((index -1) / 2, temp);
			}
			index = (index -1) / 2;
		}
	}
	
	public int peek() {
		return smallHeapArray.get(0);
	}
	
	public List<Integer> getSmallHeapArray() {
		return smallHeapArray;
	}

	public void setSmallHeapArray(List<Integer> smallHeapArray) {
		this.smallHeapArray = smallHeapArray;
	}

	public int getCount() {
		return count;
	}

	public void setCount(int count) {
		this.count = count;
	}

	public static void main(String[] args) {
		
		int[] arr = new int[] {5, 4, 6, 1, 7, 2, 3, 9, 8};
		SmallRootHeap smallRootHeap = new SmallRootHeap();
		smallRootHeap.init(arr);
		
		
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
		
		System.out.println("end");
	}

}
